package com.algorithm;

import java.util.Arrays;
import java.util.Random;

/**
 * 求数组中第K个最大项的问题,基本思路:
 * 将N个数读进一个数组中,再通过某种简单的算法,如冒泡排序,以递减的顺序排序,然后返回位置k上的元素
 * Created by houjinxin on 16/5/3.
 */
public class KMaxOptionType1 {

    private static int[] intArray;

    static {
        intArray = new int[2000];
        Random random = new Random();
        for (int i = 0; i < intArray.length; i++) {
            intArray[i] = random.nextInt();
        }
    }

    public static void main(String[] args) {
        int k = 10;
        Arrays.sort(intArray);
        maopao();
        for (int a : intArray) {
            System.out.println(a);
        }
        System.out.println("第" + (k + 1) + "大的是:" + intArray[k]);

    }

    /**
     * 逆序(由大到小)的冒泡排序
     */
    public static void maopao() {
        for (int i = 0; i < intArray.length; i++) {
            for (int j = i + 1; j < intArray.length; j++) {
                if (intArray[i] < intArray[j]) {
                    swap(i, j);
                }
            }
        }
    }

    /**
     * 调换两个元素的位置
     *
     * @param i 元素索引
     * @param j 元素索引
     */
    public static void swap(int i, int j) {
        int temp = intArray[i];
        intArray[i] = intArray[j];
        intArray[j] = temp;
    }
}
